import java.util.*;
import java.util.function.BiConsumer;

/**
 * Created by zhourh on 2018/6/15.
 *
 * 给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

 找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。

 哈希
 */
public class NumberOfBoomerangs {

    public static Map<Integer, Integer> factorials = new HashMap<>();

    public static void main(String[] args) {
        int[][] points = new int[][]{{0,0}, {1,0}, {-1,0}, {0,1}, {0,-1}};
        System.out.println(new NumberOfBoomerangs().numberOfBoomerangs(points));
    }

    public int numberOfBoomerangs(int[][] points) {
        if (points == null || points.length < 3) {
            return 0;
        }
        Map<Integer, Integer> distanceCountMap = new HashMap<>();
        int boomerangs = 0;
        for (int i = 0; i < points.length; i++ ) {
            distanceCountMap.clear();
            for (int j = 0; j < points.length; j++) {
                if (i == j) {
                    continue;
                }
                int distance = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) +
                        (points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
                distanceCountMap.put(distance, distanceCountMap.getOrDefault(distance, 0) + 1);
            }
            Iterator<Integer> iterator = distanceCountMap.values().iterator();
            while (iterator.hasNext()) {
                int d = iterator.next();
                if (d >= 2)  {
                    boomerangs += factorial(d);
                }
            }

        }

        return boomerangs;
    }

    public int factorial(int num) {
        if (num == 1) {
            return 1;
        }

        if (factorials.get(num) != null) {
            return factorials.get(num);
        }

        int factorial = num * (num - 1);
        factorials.put(num, factorial);
        return factorial;
    }
}
